Electronic signature schemes are a technology for electronically performing a task corresponding to the impression of a seal on a paper medium, i.e., a technology for affixing an electronic signature (hereinafter referred to as “electronic signature” or simply “signature”) to an electronic message that is stored in an electronic medium. The importance of electronic signature schemes has been growing as the Internet has been finding widespread use.
It is important in computerized contracts and authentications typified by electronic commercial transactions that the contents of messages be not forged. Electronic signature schemes are capable of verifying whether a message with an electronic signature affixed thereto has been forged or not.
The electronic signature schemes involve two entities, i.e., a signatory and a verifier. The signatory generates an electronic signature for a message, and outputs the electronic signature together with the message. The verifier receives the electronic signature together and the message output from the signatory, and verifies the legitimacy of the electronic signature.
There are two levels of security concept for the electronic signature schemes. One is unforgeability and the other strong unforgeability.
The unforgeability means that an electronic signature for a message which a legitimate signatory has not signed in the past cannot forged by another person. With the unforgeability, therefore, the other person may possibly be able to forge an electric signature different from an electric signature which has been affixed in the past to a message by the legitimate signatory. The strong unforgeability means that the other person cannot even forge such an electric signature. Most of the existing electronic signature schemes are known to satisfy the unforgeability. However, it is not clear whether the existing electronic signature schemes are capable of satisfying the strong unforgeability.
In recent years, there has been proposed a process of converting an electronic signature scheme which satisfies the unforgeability into an electronic signature scheme which satisfies the strong unforgeability (“Strongly Unforgeable Signatures Based on Computational Diffie-Hellman” See Dan Boneh, Emily Shen, and Brent Waters, In Public Key Cryptography—PKC 2006, LNCS 3958, Springer-Verlag, 2006). The proposed process makes it possible to realize an electronic signature scheme that satisfies the strong unforgeability.